#include<cstdio>
#include<string.h>
#include<string>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<set>
#include<map>
#include<stack>
#include<utility>

using namespace std;
//int main(){
//
//	const string filename = "/Users/sayan/Downloads/yelp_training_set/user_common_rating.uai";
//
//	string sLine = "";
//	std::ifstream infile;
//
//	vector< vector<pair<int,float> > > Data=vector< vector<pair<int,float> > >();
//	infile.open (filename.c_str(), std::ifstream::in); int count=0;
//	cout<<"Reading Data..";
//	int nNode=-1, nEdge = -1;
//
//
//	count = 0;
//	getline(infile, sLine); getline(infile, sLine);
//	nNode = (int)atoi(sLine.c_str());
//
//	short *cardinality=(short*)malloc(nNode*sizeof(short));
//
//	for (int line=0; line<1 && !infile.eof(); line++){
//		getline(infile, sLine);
//		count++;
//		vector<string> temp =  vector<string>();
//		string word = "";
//		for(unsigned i=0; i<sLine.length();i++){
//			if(sLine[i]==' '){
//
//				temp.push_back(word);
//				word = "";
//
//			}else{
//				word+=sLine[i];
//			}
//
//		}
//		temp.push_back(word);
//
//		for(int j=0;j<nNode;j++) cardinality[j]=(short)atoi(temp[j].c_str());
//		temp.clear();
//	}
//	 getline(infile, sLine); nEdge = (int)atoi(sLine.c_str());
//	cout<<"Number of Node:" <<nNode<<endl;
//	cout<<"Number of Edge:" <<nEdge<<endl;
//
////*********Build the Markov Network
//	 multimap<int,int> NodeToFactor;
//	 multimap<int,int> NodeAdjacencyList;
//
//	 vector<factor> Net=vector<factor>();
//	 int factorcount=0;
//
//	for (int l=0; l<nEdge && !infile.eof(); l++){
//		getline(infile, sLine);
//
//		count++;
//		vector<string> temp =  vector<string>();
//		string word = "";
//		for(unsigned i=0; i<sLine.length();i++){
//			if(sLine[i]==' '){
//				temp.push_back(word);
//				word = "";
//
//			}else{
//				word+=sLine[i];
//			}
//
//		}
//		temp.push_back(word);
//
////typedef pair<vector<int> ,vector<pair<vector<short>,float > > > factor;
//		int cliquesize = (int)atoi(temp[0].c_str());
//		if(cliquesize==2) {
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[1].c_str()),(int)atoi(temp[2].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[2].c_str()),(int)atoi(temp[1].c_str())));
//		}else if(cliquesize==3){
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[1].c_str()),(int)atoi(temp[2].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[2].c_str()),(int)atoi(temp[1].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[1].c_str()),(int)atoi(temp[3].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[3].c_str()),(int)atoi(temp[1].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[2].c_str()),(int)atoi(temp[3].c_str())));
//			NodeAdjacencyList.insert(pair<int,int>((int)atoi(temp[3].c_str()),(int)atoi(temp[2].c_str())));
//
//		}
//
//		vector<int> cliquenodes=vector<int>();
//		for(int j=0;j<cliquesize;j++){
//			int NodeID = (int)atoi(temp[j+1].c_str());
//			cliquenodes.push_back(NodeID);
//			NodeToFactor.insert(pair<int,int>(NodeID, factorcount));
//		}
//
//		vector<pair<vector<short>,float > > values = vector<pair<vector<short>,float > >();
//		Net.push_back(factor(cliquenodes,values));
//		factorcount++;
//		temp.clear(); cliquenodes.clear();
//	}
//	cout<<"Number of Clique Factor:" <<factorcount<<endl;
//
//	getline(infile, sLine);
//	for (int l=0; l<nEdge && !infile.eof(); l++){
//		getline(infile, sLine);
//		int cardfactor = 1;
//		for(unsigned j=0;j<Net[l].first.size();j++) cardfactor *= cardinality[Net[l].first[j]];
//		if(cardfactor!=(int)atoi(sLine.c_str())) { cout<<"ERROR: Factor cardinality mismatch at factor:" <<l<<endl;
//			cout<<"Nodes in the Factor: ";
//			for(unsigned j=0;j<Net[l].first.size();j++) cout <<j<<" ";
//			cout<<endl;
//			exit(EXIT_FAILURE);
//		}
//		getline(infile, sLine);
//		vector<string> temp =  vector<string>();
//		string word = "";
//		for(unsigned i=0; i<sLine.length();i++){
//			if(sLine[i]==' '){
//				temp.push_back(word);
//				word = "";
//
//			}else{
//				word+=sLine[i];
//			}
//
//		}
//		temp.push_back(word);
//
////typedef pair<vector<int> ,vector<pair<vector<short>,float > > > factor;
//
//		if(Net[l].first.size()==1){
//			for(int u=0;u<cardinality[Net[l].first[0]];u++){
//				float prob = (float)atof(temp[u].c_str());
//				if(prob!=0.0){
//					// Make the <value, prob> pair
//					vector<short> x = vector<short>();
//					x.push_back(u);
//					pair<vector<short>,float > value_prob (x,prob);
//					//Insert it in the factor
//					Net[l].second.push_back(value_prob);
//					x.clear();
//				}
//			}
//		}else if(Net[l].first.size()==2){
//			for(int u=0;u<cardinality[Net[l].first[0]];u++){
//				for(int v=0;v<cardinality[Net[l].first[1]];v++){
//					float prob = (float)atof(temp[u*cardinality[Net[l].first[1]] + v].c_str());
//					if(prob!=0.0){
//						// Make the <value, prob> pair
//						vector<short> x = vector<short>();
//						x.push_back(u); x.push_back(v);
//						pair<vector<short>,float > value_prob (x,prob);
//						//Insert it in the factor
//						Net[l].second.push_back(value_prob);
//						x.clear();
//					}
//				}
//			}
//		}else if(Net[l].first.size()==3){
//
//			for(int u=0;u<cardinality[Net[l].first[0]];u++){
//				for(int v=0;v<cardinality[Net[l].first[1]];v++){
//					for(int w=0;w<cardinality[Net[l].first[2]];w++){
//
//						float prob = (float)atof(temp[(u*cardinality[Net[l].first[1]] + v)*cardinality[Net[l].first[2]] + w].c_str());
//						if(prob!=0.0){
//							// Make the <value, prob> pair
//							vector<short> x = vector<short>();
//							x.push_back(u); x.push_back(v); x.push_back(w);
//							pair<vector<short>,float > value_prob (x,prob);
//							//Insert it in the factor
//							Net[l].second.push_back(value_prob);
//							x.clear();
//						}
//					}
//				}
//			}
//		}else {
//			cout<<"Cannot Handle clique size of more than 3, current clique size: "<< Net[l].first.size()<<endl;
//		}
//
//
//		temp.clear();
//
//	}
//
//
//
//
//
//
//
//
//
//	cout<<count<<endl;
//	infile.close();
//
//
//	Network markovnet(Net,NodeToFactor,nNode,NodeAdjacencyList);
//	Net.clear(); NodeToFactor.clear();
//	free(cardinality);
//
//	markovnet.show();
//	markovnet.showDependency();
//
//	//markovnet.evidence(evid);
////	markovnet.BEL(0); markovnet.BEL(12); markovnet.BEL(3);
////	markovnet.BEL(4); markovnet.BEL(1); markovnet.BEL(8);markovnet.BEL(2);
////	markovnet.BEL(13); markovnet.BEL(15); markovnet.BEL(5);markovnet.BEL(7); markovnet.BEL(9);
////
////	markovnet.BEL(6); markovnet.BEL(14); markovnet.BEL(10);
//
//	vector<int> elimorder= vector<int>(); int InducedWidth;
//
//	int i=1;
//		elimorder.clear();
//		Network N(markovnet);
//		N.getEliminationOrder(elimorder,InducedWidth,i);
//		for(unsigned j=0;j<elimorder.size();j++) cout<<elimorder[j]<<" ";
//		cout<<endl;
//		cout<<endl<<"Induced Width: "<<InducedWidth<<" for Marginal On:"<<i<<endl;
////		factor F = N.getMarginal(elimorder,i);
////
////		for(unsigned j=0;j<F.second.size();j++) cout<<F.second[j].first[0]<<": "<<F.second[j].second<<" ";
////		cout<<endl;
//
//
//
//
//
//
//
//
//
//
//	cout<<"*******FInished All Operations******" <<endl;
//
//
//
//
//
//
//	//markovnet.showDependency();
//
//}
